package com.coolingme.algo_01_list.addtwolist;

/**
 * 添加两个链表
 * <p>
 * input:  <br/>
 * 2 -> 4 -> 3<br/>
 * 5 -> 6 -> 4<br/>
 * output: 7 -> 0 -> 8
 * <p>
 * 解释：342 + 564 = 708
 *
 * @author wangyue
 * @date 2020/11/5 15:14
 */
public class AddTwoList {

    public static ListNode add(ListNode n1, ListNode n2) {
        if (n1 == null) {
            return null;
        }
        if (n2 == null) {
            return null;
        }
        // 进位
        int carry = 0;
        // 给结果列表加一个头
        ListNode head = new ListNode(-1);
        // 当前结果列表执行到的头，相当于指针
        ListNode pre = head;

        // 循环两个链表相加
        // 链表长度相等
        while (n1 != null && n2 != null) {
            // 和
            int sum = n1.value + n2.value + carry;
            // 当前进位，0或1
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            // 连接链表
            pre.next = node;
            // 向后移位
            pre = pre.next;
            n1 = n1.next;
            n2 = n2.next;
        }

        // 链表长度不相等
        while (n1 != null) {
            int sum = n1.value + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            pre.next = node;
            pre = pre.next;
            n1 = n1.next;
        }
        while (n2 != null) {
            int sum = n2.value + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            pre.next = node;
            pre = pre.next;
            n2 = n2.next;
        }

        // 链表长度相等，但最后n1+n2有进位
        if (carry == 1) {
            ListNode node = new ListNode(carry);
            pre.next = node;
        }

        return head.next;
    }

    public static void main(String[] args) {

        ListNode n1 = new ListNode(2);
        ListNode n1_a = n1.setNext(4);
        n1_a.setNext(3);

        // 两个链表长度相等
        ListNode n2 = new ListNode(5);
        ListNode n2_a = n2.setNext(6);
        n2_a.setNext(4);

        // 两个链表长度不相等
        ListNode n3 = new ListNode(5);
        ListNode n3_a = n3.setNext(6);
        ListNode n3_b = n3_a.setNext(4);
        n3_b.setNext(6);

        // 两个链表长度相等，但最后n1+n2有进位
        ListNode n4 = new ListNode(5);
        ListNode n4_a = n4.setNext(6);
        n4_a.setNext(7);

        ListNode sumNode = add(n1, n2);
        System.out.println("\n两个链表长度相等");
        System.out.println("input:\n" + n1 + "\n" + n2);
        System.out.println("output:\n" + sumNode);

        ListNode sumNode2 = add(n1, n3);
        System.out.println("\n两个链表长度不相等");
        System.out.println("input:\n" + n1 + "\n" + n3);
        System.out.println("output:\n" + sumNode2);

        ListNode sumNode3 = add(n1, n4);
        System.out.println("\n两个链表长度相等，但最后n1+n2有进位");
        System.out.println("input:\n" + n1 + "\n" + n4);
        System.out.println("output:\n" + sumNode3);
    }

}
